/**
 * ANSWER: 291504964
 */

#include <iostream>
#include "static.h"
#include "modulo.h"

void solve_problem_340()
{
#if 0
	typedef unsigned int number_t;
	const number_t a = 50, b = 2000, c = 40;
	const number_t l = (b+1)/a, r = b+1-l*a;

	// Let s_x = x*(x-1)/2.
	const number_t s_a = a*(a-1)/2;
	const number_t s_l = l*(l-1)/2;
	const number_t s_r = r*(r-1)/2;

#else
	const long long aa = static_pow<21,7>::value;
	const long long bb = static_pow<7,21>::value;
	const long long cc = static_pow<12,7>::value;
	const long long ll = (bb+1) / aa;
	const long long rr = bb+1-ll*aa;

	// Let s_x = x*(x-1)/2.
	const long long s_a = aa*(aa-1)/2;
	const long long s_l = ll*(ll-1)/2;
	const long long s_r = rr*(rr-1)/2;

	typedef modulo<1000000000> number_t;
	const number_t a = aa, b = bb, c = cc, l = ll, r = rr;
#endif

	number_t d = a - c;
	number_t s1 = 3*d*r*l + (b+4*d)*r - s_r;
	number_t s2 = 3*d*a*s_l + (b+4*d)*a*l - s_a*l;
	number_t s = s1 + s2;

	std::cout << s << std::endl;
}
